<?php
/**
 * @title 95. 不同的二叉搜索树 II - 递归
 * @author start2004
 */


class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}


class Solution {

    /**
     * @param Integer $n
     * @return TreeNode[]
     */
    function generateTrees($n) {
        /**
         * @since 2020-07-21 特殊情况先行排除
         */
        if($n == 0){
            return [];
        } else {}

        /**
         * @since 2020-07-21 节点
         */
        $nodes = [];
        for($i=1; $i<=$n; $i++){
            $nodes[] = $i;
        }

        /**
         * @since 2020-07-21 获取子树
         */
        $trees = self::tree($nodes);
        return $trees;

        /**
         * @since 2020-07-21 转成数组
         */
        $data = self::toArray($trees);

        /**
         * @return
         */
        return $data;
    }


    /**
     * @title 返回二叉树
     * @author start2004
     * @since 2020-07-21 Created
     *
     * @param array $nodes
     * @return array
     */
    function tree($nodes = []){
        $len = count($nodes);
        // echo str_repeat(PHP_EOL, 2), "nodes=[", implode(", ", $nodes) ,"]", PHP_EOL;

        /**
         * @since 2020-07-21 单独处理长度0和1
         */
        if($len == 0){
            return [null];
        } elseif($len == 1){
            return [new TreeNode($nodes[0])];
        } else {}

        /**
         * @since 2020-07-21 root节点从左往右移动, shift, push
         * @since 2020-07-21 避免使用array_slice
         */
        $midNode = array_shift($nodes);
        $leftNodes = [];
        $rightNodes = $nodes;

        /**
         * @since 2020-07-21 递归
         */
        $result = [];
        for($i=1; $i<=$len; $i++){
            // echo "mid={$midNode}, left=[", implode(", ", $leftNodes) ,"], right=[", implode(", ", $rightNodes) ,"]", PHP_EOL;

            /**
             * @since 2020-07-21 左右子树
             */
            $leftTrees = self::tree($leftNodes);
            $rightTrees = self::tree($rightNodes);

            /**
             * @since 2020-07-21 根节点
             */
            foreach ($leftTrees as $left){
                foreach ($rightTrees as $right){
                    $root = new TreeNode($midNode);
                    $root->left = $left;
                    $root->right = $right;
                    $result[] = $root;
                    // unset($root);
                }
            }

            /**
             * @since 2020-07-21 root向右移动
             */
            array_push($leftNodes, $midNode);
            $midNode = array_shift($rightNodes);
        }

        /**
         * @return
         */
        return $result;
    }

    /**
     * @title 二叉树转成数组
     * @author start2004
     * @since 2020-07-21 Created
     *
     * @param array $trees
     * @return array
     */
    function toArray($trees = []){
        $result = [];

        /**
         * @since 2020-07-21 二叉树转array
         */
        foreach ($trees as $tree){
            $arr = [];
            $currentTree = [$tree];
            while($currentTree){
                $nextTree = [];

                /**
                 * @since 2020-07-21 一层一层往下
                 */
                foreach ($currentTree as $root){
                    if($root === null){
                        $arr[] = null;
                    } else {
                        $arr[] = $root->val;
                        $nextTree[] = $root->left;
                        $nextTree[] = $root->right;
                    }
                }

                /**
                 * @since 2020-07-21 下次循环
                 */
                $currentTree = $nextTree;
            }

            /**
             * @since 2020-07-21 去掉末尾null
             */
            for($i=count($arr)-1; $i>=0; $i--){
                if($arr[$i] === null){
                    unset($arr[$i]);
                } else {
                    break;
                }
            }
            $result[] = $arr;
        }

        /**
         * @return
         */
        return $result;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.21.php
 */
$datas = [
    8,
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->generateTrees($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
